""" 欢迎关注 "码农架构" 微信公众号，热爱开源，拥抱开源。一个IT民工的技术之路经验分享。
    - 问题咨询 / 建议
    1.关注微信公众号 "码农架构" 后私信
    2.可发送邮件: li.shangzhi@aliyun.com
"""
# !/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2019/12/27 23:48
# @Author  : iByte

# 丢番图方程：给定整数a，b，c（a和b中的至少一个！=0），丢番图方程

# a*x+b*y=c有一个解（其中x和y是整数）iff gcd（a，b）除以c。

# GCD（最大公约数）或HCF（最大公约数）


def diophantine(a, b, c):
    """
    >>> diophantine(10,6,14)
    (-7.0, 14.0)
    >>> diophantine(391,299,-69)
    (9.0, -12.0)
    但上面的方程还有一个解，即x=-4，y=5。
    这就是我们需要丢番图全解函数的原因
    """

    assert (
        c % greatest_common_divisor(a, b) == 0
    )
    (d, x, y) = extended_gcd(a, b)
    r = c / d
    return (r * x, r * y)


def diophantine_all_soln(a, b, c, n=2):

    """
    >>> diophantine_all_soln(10, 6, 14)
    -7.0 14.0
    -4.0 9.0
    >>> diophantine_all_soln(10, 6, 14, 4)
    -7.0 14.0
    -4.0 9.0
    -1.0 4.0
    2.0 -1.0
    >>> diophantine_all_soln(391, 299, -69, n = 4)
    9.0 -12.0
    22.0 -29.0
    35.0 -46.0
    48.0 -63.0
    """
    (x0, y0) = diophantine(a, b, c)
    d = greatest_common_divisor(a, b)
    p = a // d
    q = b // d

    for i in range(n):
        x = x0 + i * q
        y = y0 - i * p
        print(x, y)


# 欧几里得引理：d除a和b，当且仅当d除a-b和b
# 欧几里得算法


def greatest_common_divisor(a, b):
    """
    >>> greatest_common_divisor(7,5)
    1
    注：在数论中，两个整数a和b被称为相对素数、互素数或共素数,如果将两者分开的唯一正整数（因子）是1，即gcd（a，b）=1。
    >>> greatest_common_divisor(121, 11)
    11
    """
    if a < b:
        a, b = b, a

    while a % b != 0:
        a, b = b, a % b

    return b


# 扩展欧几里得算法：如果d除以a和b，d=a*x+b*y，则d=gcd（a，b）
def extended_gcd(a, b):
    """
    >>> extended_gcd(10, 6)
    (2, -1, 2)
    >>> extended_gcd(7, 5)
    (1, -2, 3)
    """
    assert a >= 0 and b >= 0

    if b == 0:
        d, x, y = a, 1, 0
    else:
        (d, p, q) = extended_gcd(b, a % b)
        x = q
        y = p - q * (a // b)

    assert a % d == 0 and b % d == 0
    assert d == a * x + b * y

    return (d, x, y)


# 导入testmod以测试我们的函数
from doctest import testmod

if __name__ == "__main__":
    testmod(name="diophantine", verbose=True)
    testmod(name="diophantine_all_soln", verbose=True)
    testmod(name="extended_gcd", verbose=True)
    testmod(name="greatest_common_divisor", verbose=True)